
public class Sort {
    private int[] heap;
    private int size;

    public Sort(int length) {
        heap = new int[length + 1];
        this.size = 0;
    }

    public Sort() {

    }

    public void insert(int n) {
        heap[size + 1] = n;
        shiftUp(size + 1);
        size++;
    }

    public int pop() {
        int res = heap[1];
        heap[1] = heap[size];
        size--;
        shiftDown(1);
        return res;
    }

    private void shiftDown(int k) {
        while (k * 2 <= size) {
            int j = k * 2;
            if (j + 1 <= size && heap[j] <= heap[j + 1]) {
                j++;
            }
            if (heap[k] <= heap[j]) {
                int temp = heap[k];
                heap[k] = heap[j];
                heap[j] = temp;
                k = j;
            } else {
                break;
            }
        }
    }

    private void shiftUp(int k) {
        while (k > 1 && heap[k / 2] <= heap[k]) {
            int temp = heap[k / 2];
            heap[k / 2] = heap[k];
            heap[k] = temp;
            k /= 2;
        }
    }

    public void heapify(int[] nums) {
        heap = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            heap[i + 1] = nums[i];
        }
        size = nums.length;
        int n = nums.length / 2;
        while (n >= 1) {
            shiftDown(n);
            n--;
        }
    }

    //原地排序
    public void sort(int[] nums, int n) {
        for (int i = (n - 1) / 2; i >= 0; i--) {
            shiftDown(nums, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            shiftDown(nums, i, 0);
        }
    }

    private void shiftDown(int[] nums, int n, int k) {
        while (k * 2 + 1 < n) {
            int j = k * 2 + 1;
            if (j + 1 < n && nums[j] <= nums[j + 1]) {
                j++;
            }
            if (nums[k] <= nums[j]) {
                int temp = nums[k];
                nums[k] = nums[j];
                nums[j] = temp;
                k = j;
            } else {
                break;
            }
        }
    }

    public void print() {
        for (int i = 1; i <= size; i++) {
            System.out.print(heap[i] + " ");
        }
    }

    public void print(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static void main(String[] args) {
        Sort sort = new Sort();
        int[] nums = {2, 6, 4, 78, 11, 0, 44, 37};
        sort.sort(nums, 8);
        sort.print(nums);
    }

}
